package 动态规划;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : 最大收益的切割方案
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/5/5 17:44
 */
public class 最大收益的切割方案 {
    public static void main(String[] args) {
        int[] price = {1, 6, 5, 4, 4};
        int totalLen = 5;
        System.out.println(topDown(price, totalLen));
        System.out.println(bottomUp(price, totalLen));
    }

    // 自顶向上
    public static int topDown(int[] price, int totalLen) {
        int profit = 0;
        if (totalLen <= 0) {
            return 0;
        }
        for (int i = 1; i <= totalLen; i++) {
            int temp = price[i-1] + topDown(price, totalLen - i);
            profit = Math.max(profit, temp);
        }
        return profit;
    }
    // 自底向上
    public static int bottomUp(int[] price, int totalLen) {
        int[] dp = new int[totalLen + 1];
        for (int i = 1; i <= totalLen; i++) {
            int temp = 0;
            for (int j = 1; j <= i; j++) {
                temp = Math.max(temp, dp[j] + dp[i - j]);
            }
            dp[i] = Math.max(price[i-1], temp);
        }
        return dp[totalLen];
    }
}
